package leetcode_81_100;

import java.util.Arrays;

public class merge_88 {
    /**
     * 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。（即后一个元素只能大于等于前一个元素）
     * 合并后数组不应由函数返回，而是存储在数组 nums1 中
     * @param nums1 按 非递减顺序 排列的整数数组 , 初始长度为 m + n
     * @param m nums1 中的元素数目
     * @param nums2
     * @param n nums2 中的元素数目
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        /**
         * 很蠢的方法，利用第三个数组
         * 但是0ms
         */
        if(n==0)
            return;
        int index1=0,index2=0,copyIdx=0;
        int [] copy=new int[m+n];
        while (copyIdx<m+n){
             if(index2!=n&&nums2[index2]<=nums1[index1]){ //nums2当前元素小于等于nums1当前元素
                 copy[copyIdx++]=nums2[index2++];
             }else if(index1< m)
                 copy[copyIdx++]=nums1[index1++];
             else
                 copy[copyIdx++]=nums2[index2++];
        }
        index1=0;
        for (int i:copy)
            nums1[index1++]=i;
    }

    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        /**
         * 尝试在原地址修改
         * 从两个数组的实际尾部比较, 更大的元素去填充nums1的尾部
         */
        int index1=m-1,index2=n-1,index3=m+n-1;
        while (index2>=0){
            if(index1<0 || nums2[index2]>=nums1[index1]){//若nums1元素使用完毕，或者nums2此时尾部元素更大
                nums1[index3--] = nums2[index2--]; // nums2去填充nums1的尾部
            } else {
                nums1[index3--] = nums1[index1];
                nums1[index1]=0;  //nums1更大则进行调换
                index1--;
            }
        }
    }
}
